package com.review.dp;

public class LC_416 {
    // 回溯法遇到稍微大一点的数据就会超时
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        return dp(nums, sum / 2, 0);
    }

    public static boolean dp(int[] nums, int res, int index) {
        if (res == 0) {
            return true;
        }
        if (index == nums.length) {
            return false;
        }
        if (res < 0) {
            return false;
        }
        return dp(nums, res - nums[index], index + 1) || dp(nums, res, index + 1);
    }

    // 动态规划
    public static boolean canPartition_2(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum /= 2;
        int[] dp = new int[sum + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = sum; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[sum] == sum;
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 2, 3, 5}));
        System.out.println(canPartition_2(new int[]{1, 5, 11, 5}));
    }
}
